package leetcode.binarysearch;

/**
 * 
 * @author 26233
 *
 *
 *给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode34_SearchRange {
	
	public static int[] searchRange(int[] nums, int target) {
		if((nums.length == 1 && target != nums[0]) || nums.length < 1)return new int[]{-1, -1};
		int p = 0, q = nums.length - 1;
		while(p < q) {
			int temp = (p + q) / 2;
			if(nums[temp] == target) {
				p = q = temp;
				while(p > 0) {
					if(nums[p - 1] == target) {
						p--;
					}else break;
				}
				while(q <= nums.length - 2) {
					if(nums[q + 1] == target) {
						q++;
					}else break;
				}
				break;
			}else {
				if(nums[temp] > target) {
					q = (p + q) / 2;
				}else if(nums[temp] < target ) {
					p = (p + q) / 2;
				}
			}
			if(p + 1 == q) {
				if(nums[p] == target) {
					q = p;
				}else if(nums[q] == target){
					p = q;
				}else break;
			}
		}
		return nums[p] == target ? new int[]{p, q} : new int[] {-1, -1};
    }
	
	public static void main(String[] args) {
		System.out.println(searchRange(new int[] {1,4}, 4));
	}

}
